public class Code02_HeapSort {
    // 对给定的整数数组进行排序并返回排序后的数组
    public static int[] sortArray(int[] nums) {
        // 如果数组长度大于1才进行排序操作
        if (nums.length > 1) {
            // heapSort1为从顶到底建堆然后排序
            // heapSort2为从底到顶建堆然后排序
            // 这里可以使用其中任何一个方法进行排序
            // heapSort1(nums);
            heapSort2(nums);
        }
        return nums;
    }

    // i位置的数，向上调整大根堆
    // 假设arr[i] = x，x是新加入堆中的数，向上调整直到不比父亲大，或者来到0位置(堆顶)
    public static void heapInsert(int[] arr, int i) {
        // 只要当前节点的值大于其父节点的值
        while (arr[i] > arr[(i - 1) / 2]) {
            // 交换当前节点和其父节点的值
            swap(arr, i, (i - 1) / 2);
            // 更新当前节点的索引为父节点的索引，继续向上比较
            i = (i - 1) / 2;
        }
    }

    // i位置的数，变小了，又想维持大根堆结构
    // 向下调整大根堆，当前堆的大小为size
    public static void heapify(int[] arr, int i, int size) {
        // 左孩子的索引
        int l = i * 2 + 1;
        while (l < size) {
            // 有左孩子，l
            // 右孩子，l + 1
            // 评选，最强的孩子（值最大的孩子），是哪个下标的孩子
            // 如果有右孩子，就判断右孩子和左孩子的数哪个大
            // 如果没有右孩子，就直接让左孩子当最强的孩子
            int best = l + 1 < size && arr[l + 1] > arr[l]? l + 1 : l;
            // 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
            best = arr[best] > arr[i]? best : i;
            if (best == i) {
                // 如果当前节点已经是最大的（和它的孩子相比），则不需要调整，直接退出
                break;
            }
            // 交换当前节点和最强孩子节点的值
            swap(arr, best, i);
            // 更新当前节点的索引为最强孩子的索引
            i = best;
            // 更新左孩子的索引
            l = i * 2 + 1;
        }
    }

    // 交换数组中两个位置的元素
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 从顶到底建立大根堆，时间复杂度为O(n * logn)
    // 依次弹出堆内最大值并排好序，时间复杂度为O(n * logn)
    // 整体时间复杂度为O(n * logn)
    public static void heapSort1(int[] arr) {
        int n = arr.length;
        // 从第一个元素开始，逐个将元素向上调整构建大根堆
        for (int i = 0; i < n; i++) {
            heapInsert(arr, i);
        }
        int size = n;
        while (size > 1) {
            // 将堆顶（最大值）与堆的最后一个元素交换
            swap(arr, 0, --size);
            // 对新的堆顶元素向下调整以维持大根堆结构
            heapify(arr, 0, size);
        }
    }

    // 从底到顶建立大根堆，时间复杂度为O(n)
    // 依次弹出堆内最大值并排好序，时间复杂度为O(n * logn)
    // 整体时间复杂度为O(n * logn)
    public static void heapSort2(int[] arr) {
        int n = arr.length;
        // 从最后一个非叶子节点开始，逐个将元素向下调整构建大根堆
        for (int i = n - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
        int size = n;
        while (size > 1) {
            // 将堆顶（最大值）与堆的最后一个元素交换
            swap(arr, 0, --size);
            // 对新的堆顶元素向下调整以维持大根堆结构
            heapify(arr, 0, size);
        }
    }
}